---

deList.hpp

Go to the documentation of this file.

///////////////////////////////////////////////////////////////////////////////
/// @file deList.hpp
///
/// @brief Templated linked list class
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Sept 2001
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DELIST_HPP
#define DELIST_HPP

#include "deGlobalTypes.hpp"

#ifndef NULL
#define NULL (0)
#endif

#pragma warning (disable : 4284) // return type for 'identifier::operator ->' is not a UDT or reference to a UDT. Will produce errors if applied using infix notation

/// templated linked-list storage class
template <class T>
class deTList
{
private:
    class TListNode
    {
    public:
        TListNode()
            :Next(NULL), Prev(NULL)
            {
            #ifdef _DEBUG
            List = NULL;
            #endif
            }
        TListNode(const T & ref)
            :Data(ref), Next(NULL), Prev(NULL)
            {
            #ifdef _DEBUG
            List = NULL;
            #endif
            }
        TListNode(const TListNode & ref)
            :Data(ref.Data), Next(NULL), Prev(NULL)
            {
            #ifdef _DEBUG
            List = NULL;
            #endif
            }
        virtual ~TListNode()
            {}

        TListNode *Next, *Prev;
        #ifdef _DEBUG
        deTList * List;
        #endif
        T Data;
    };

public:
    class iterator
    {
    private:
        friend class deTList<T>;
        TListNode* m_Node;
    protected:
        iterator(TListNode* node) : m_Node(node) {}
    public:
        iterator() : m_Node(0) {}
        ~iterator() {}
        T& operator*() const
        {
            DE_ASSERT (m_Node != 0);
            return m_Node->Data;
        }
        T* operator->() const { return &operator*(); }
        void operator++() { m_Node = m_Node->Next; }
        void operator--() { m_Node = m_Node->Prev; }
        bool operator==(const iterator & other) const
            { return m_Node == other.m_Node; }
        bool operator!=(const iterator & other) const
            { return m_Node != other.m_Node; }
    };

private:
    TListNode *m_Front, *m_Back;
    long m_Length;

public:
    deTList()
    {
        m_Front = NULL;
        m_Back = NULL;
        m_Length = 0;
    }
    deTList(const deTList <T> & ref)
    {
        TListNode *Node = ref.m_Front, *NewNode = NULL, *tempnode = NULL;
        m_Front = NULL;
        m_Back = NULL;
        m_Length = 0;

        if (Node)
        {
            NewNode = new TListNode(Node->Data);
            #ifdef _DEBUG
            NewNode->List = this;
            #endif
            m_Front = NewNode;
            tempnode = NewNode;
            Node = Node->Next;
        }
        while(Node)
        {
            NewNode = new TListNode(Node->Data);
            #ifdef _DEBUG
            NewNode->List = this;
            #endif
            NewNode->Prev = tempnode;
            tempnode = NewNode;
            Node = Node->Next;
        }
        m_Back = NewNode;
        m_Length = ref.m_Length;
    }
    const deTList <T> & operator=(const deTList <T> & ref)
    {
        TListNode *Node = ref.m_Front, *NewNode = NULL, *tempnode = NULL;
        EmptyList();

        if (Node)
        {
            NewNode = new TListNode(Node->Data);
            #ifdef _DEBUG
            NewNode->List = this;
            #endif
            m_Front = NewNode;
            tempnode = NewNode;
            Node = Node->Next;
        }
        while(Node)
        {
            NewNode = new TListNode(Node->Data);
            #ifdef _DEBUG
            NewNode->List = this;
            #endif
            NewNode->Prev = tempnode;
            if (tempnode)
                tempnode->Next = NewNode;
            tempnode = NewNode;
            Node = Node->Next;
        }
        m_Back = NewNode;
        m_Length = ref.m_Length;

        return *this;
    }
    ~deTList()
    {
        EmptyList();
    }

    void EmptyList()
    {
        TListNode *ptr1, *ptr2;
        ptr1 = m_Front;
        while(ptr1 != NULL)
        {
            ptr2 = ptr1->Next;
            delete ptr1;
            ptr1 = ptr2;
        }
        m_Front = m_Back = NULL;
        m_Length = 0;
    }
    void* FindData(void* current, T & data) const
    {
        void* ptr = current;
        T* temp;
        if (ptr)
            GetData(ptr, temp);
        else
            ptr = GetNext(NULL, temp);
        while( ptr && !(*temp == data))
        {
            ptr = GetNext(ptr, temp);
        }
        return ptr;
    }
    void* GetNext(void* current, T * & ptr) const
    {
        TListNode *Node = (TListNode*)current;
        if (Node)
        {
            if (Node->Next)
                Node = Node->Next;
            else
            {
                ptr = NULL;
                return NULL;
            }
        }
        else
        {
            if (m_Front)
                Node = m_Front;
            else
            {
                ptr = NULL;
                return NULL;
            }
        }
        ptr = &(Node->Data);
        return Node;
    }
    void* GetNext(void* current, T & obj) const
    {
        T * objptr;
        void * ptr;
        ptr = GetNext(current, objptr);
        if (objptr)
            obj = *objptr;
        return ptr;
    }
    void* GetPrev(void* current, T * & ptr) const
    {
        TListNode *Node = (TListNode*)current;
        if (Node)
        {
            if (Node->Prev)
                Node = Node->Prev;
            else
            {
                ptr = NULL;
                return NULL;
            }
        }
        else
        {
            if (m_Back)
                Node = m_Back;
            else
            {
                ptr = NULL;
                return NULL;
            }
        }
        ptr = &(Node->Data);
        return Node;
    }
    void* GetPrev(void* current, T & obj) const
    {
        T * objptr;
        void * ptr;
        ptr = GetPrev(current, objptr);
        if (objptr)
            obj = *objptr;
        return ptr;
    }
    void GetData(void * current, T & obj) const
    {
        const TListNode *Node = (const TListNode*)current;
        if (Node)
            obj = (Node->Data);
    }
    void GetData(void * current, const T* & obj) const
    {
        const TListNode *Node = (const TListNode*)current;
        if (Node)
            obj = &(Node->Data);
    }
    void* AddElementNoData()
    {
        TListNode * Node = new TListNode();
        if (!Node)
            return NULL;
        #ifdef _DEBUG
        Node->List = this;
        #endif
        m_Length++;
        if (m_Front == NULL)
            m_Front = Node;
        if (m_Back)
            m_Back->Next = Node;
        Node->Prev = m_Back;
        m_Back = Node;
        
        return Node;
    }
    void* AddElement(const T & data)
    {
        TListNode * Node = new TListNode(data);
        if (!Node)
            return NULL;
        #ifdef _DEBUG
        Node->List = this;
        #endif
        m_Length++;
        if (m_Front == NULL)
            m_Front = Node;
        if (m_Back)
            m_Back->Next = Node;
        Node->Prev = m_Back;
        m_Back = Node;

        return Node;
    }
    void* AddElementBefore(const T & data, void * current)
    {
        TListNode * Node = (TListNode*)current;
        if (!Node)
        {
            Node = m_Front;
            if (!Node)
            {
                return AddElement(data);
            }
        }
        TListNode * NewNode = new TListNode(data);
        if (!NewNode)
            return NULL;
        #ifdef _DEBUG
        NewNode->List = this;
        #endif
        m_Length++;
        NewNode->Prev = Node->Prev;
        NewNode->Next = Node;
        if (Node->Prev)
            Node->Prev->Next = NewNode;
        else
            m_Front = NewNode;
        Node->Prev = NewNode;
        
        return NewNode;
    }
    void* AddElementAfter(const T & data, void * current)
    {
        TListNode * Node = (TListNode*)current;
        if (!Node)
        {
            Node = m_Back;
            if (!Node)
            {
                return AddElement(data);
            }
        }
        TListNode * NewNode = new TListNode(data);
        if (!NewNode)
            return NULL;
        #ifdef _DEBUG
        NewNode->List = this;
        #endif
        m_Length++;
        NewNode->Next = Node->Next;
        NewNode->Prev = Node;
        if (Node->Next)
            Node->Next->Prev = NewNode;
        else
            m_Back = NewNode;
        Node->Next = NewNode;
        
        return NewNode;
    }
    void AppendList(const deTList <T> & list)
    {
        TListNode *Node, *NodeCopy=NULL;
        Node = list.m_Front;
        while (Node != NULL)
        {
            NodeCopy = new TListNode(Node->Data);
            #ifdef _DEBUG
            NodeCopy->List = this;
            #endif
            if (!m_Back)
            {
                m_Back = NodeCopy;
                m_Front = NodeCopy;
            }
            else
            {
                m_Back->Next = NodeCopy;
                NodeCopy->Prev = m_Back;
                //NodeCopy->Next = NULL;
                m_Back = NodeCopy;
            }
            Node = Node->Next;
        }
        if (NodeCopy)
            NodeCopy->Next = NULL;
        m_Length += list.m_Length;
    }
    void MergeList(deTList <T> & list)
    {
        TListNode *Node;
        Node = list.m_Front;
        if (!m_Back)
        {
            m_Back = Node;
            m_Front = Node;
        }
        else
        {
            m_Back->Next = Node;
            Node->Prev = m_Back;
            m_Back = Node;
        }
        #ifdef _DEBUG
        while (Node != NULL)
        {
            Node->List = this;
            Node = Node->Next;
        }
        #endif
        m_Length += list.m_Length;
        list.m_Length = 0;
        list.m_Front = list.m_Back = NULL;
    }
    #ifdef _DEBUG
    static void StaticRemoveElement(void * ptr)
    {
        TListNode * Node = (TListNode*)ptr;
        if (Node->List)
            Node->List->RemoveElement(ptr);
    }
    #endif
    deBoolean RemoveElement(void * ptr)
    {
        TListNode * Node = (TListNode*)ptr;
        if (Node == NULL)
            return deTRUE;
        #ifdef _DEBUG
        if (Node->List != this)
            return deFALSE;
        #endif
        m_Length--;
        if (Node->Prev)
            Node->Prev->Next = Node->Next;
        if (Node->Next)
            Node->Next->Prev = Node->Prev;
        if (m_Front == Node)
            m_Front = Node->Next;
        if (m_Back == Node)
            m_Back = Node->Prev;
        Node->Next = NULL;
        Node->Prev = NULL;
        #ifdef _DEBUG
        Node->List = NULL;
        #endif
        delete Node;
        return deTRUE;
    }
    inline void * RemoveElementGetNext(void* current, T * & ptr)
    {
        void * ret;
        ret = GetNext(current, ptr);
        RemoveElement(current);
        return ret;
    }

    inline long Length() const  { return m_Length; }
    inline long size() const    { return m_Length; }

    // iterator stuff
    iterator push_back(const T & data)
    {
        TListNode * Node = (TListNode*)AddElement(data);
        return iterator(Node);
    }
    iterator push_back()
    {
        TListNode * Node = (TListNode*)AddElementNoData();
        return iterator(Node);
    }

    inline iterator begin() { return iterator(m_Front); }
    inline iterator end()   { return iterator(0); }

    inline iterator erase(iterator& it)
    {
        iterator next = it;
        ++next;
        RemoveElement(it.m_Node);
        return next;
    }
};


//#pragma warning (default : 4710)

#endif

---